package Solution151_175;

import org.junit.Test;

import java.util.Stack;

public class Solution173 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class BSTIterator {

        private Stack<TreeNode> stack=new Stack<>();
        public BSTIterator(TreeNode root) {
            if(root!=null){
                stack.push(root);
            }
        }

        /**
         * @return the next smallest number
         */
        public int next() {
            TreeNode curNode=stack.pop();
            while (curNode.left!=null){
                /*剪枝*/
                TreeNode temp=curNode.left;
                curNode.left=null;
                stack.push(curNode);
                curNode=temp;
            }
            if(curNode.right!=null){
                stack.push(curNode.right);
            }
            return curNode.val;
        }

        /**
         * @return whether we have a next smallest number
         */
        public boolean hasNext() {
            return stack.size()!=0;
        }
    }

    @Test
    public void test(){
        TreeNode root=new TreeNode(7);
        TreeNode treeNode2=new TreeNode(3);
        TreeNode treeNode3=new TreeNode(15);
        root.left=treeNode2;
        root.right=treeNode3;
        TreeNode treeNode4=new TreeNode(9);
        TreeNode treeNode5=new TreeNode(20);
        treeNode3.left=treeNode4;
        treeNode3.right=treeNode5;

        BSTIterator iterator = new BSTIterator(root);
        System.out.println(iterator.next());    // 返回 3
        System.out.println(iterator.next());    // 返回 7
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 9
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 15
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());    // 返回 20
        System.out.println(iterator.hasNext()); // 返回 false

    }
}
